﻿#include <iostream>

typedef char TElemType;
TElemType Nil = '#';
#define MaxTreeSize 9

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;


void InitBiTree(BiTree &BT) {
    BT = NULL;
}

void CreatBiTree(BiTree &BT) {
    TElemType e;
    std::cin >> e;
    if (e == Nil)
        BT = NULL;
    else {
        BT = (BiTNode *) malloc(sizeof(BiTNode));
        if (!BT) exit(-1); // 申请新结点失败
        BT->data = e;
        CreatBiTree(BT->lchild);  // 递归构造左子树
        CreatBiTree(BT->rchild);  // 递归构造右子树
    }
}

void Visit(BiTree BT) {
    printf("%c", BT->data);
}

int TreeDepth(BiTree BT) {
    int Lh, Rh;
    if (!BT)
        return 0;
    Lh = TreeDepth(BT->lchild);
    Rh = TreeDepth(BT->rchild);
    return Lh > Rh ? Lh + 1 : Rh + 1;
}


/*
 * 二叉树按照二叉链表形式存储，试标写一个判定给定二叉树是否是完全二叉树的算法
 * 分析：完全二叉树要求按从左到右，从上到下的对结点进行编号，当且仅当每个结点斗鱼满二叉树一一对应时，称为完全二叉树。
 * 操作步骤：采用层次遍历算法，将所有结点加入队列（包括空结点）。遇到空结点时，查看其后是否有非空结点。若有，则二叉树不是完全二叉树。
 */
int Is_Completed_BiTree(BiTree BT) {
    if (BT == NULL) {
        return 0;
    }
    BiTNode *queue[MaxTreeSize];
    BiTNode *p;
    int front = 0, rear = 0;
    queue[rear++] = BT;  // 根结点入队
    while (front != rear) {
        p = queue[front++];
        if (p) {  // 结点非空，将其左、右子树入队列
//            std::cout << p->data;
            queue[rear++] = p->lchild;
            queue[rear++] = p->rchild;
        } else {   // 结点为空，检查其后是否有给非空结点
            while (front != rear) {
                p = queue[front++];
                if (p)  // 结点非空，则二叉树不是完全二叉树
                    return 0;
            }
        }
    }
    return 1;
}


int main() {
    BiTree BT;
    InitBiTree(BT);
    printf("创建一棵二叉树,请按照前序序列输入树中的结点（'#'表示子树为空）：\n");
    CreatBiTree(BT);

    printf("是否是完全二叉树？");
    int flag = Is_Completed_BiTree(BT);
    if (flag)
        printf("是完全二叉树");
    else
        printf("不是完全二叉树");

    return 0;
}